
/**
 * 插入排序实现原理:
 * 插入排序是一种简单直观的排序算法，适用于小规模数据或部分有序的数据集。
 * 它的工作原理类似于整理扑克牌，通过构建有序序列，对于未排序数据，在已
 * 排序序列中从后向前扫描，找到相应位置并插入。总结一句话就是:
 * 第一个元素默认已排好，第i个元素依次与第i-1 ~ 0 个元素比较，
 * 大于i号元素的就往后移一位，小于等于i号元素的，i号元素就插入在其后，
 * 结束此趟排序。
 *
 * 最坏时间复杂度：1 + 2 + 3 + ... + n = O(n^2)
 * 最好时间复杂度：O(n)，基本有序
 * 空间复杂度：O(1)
 *
 * 最坏时间复杂度（倒序）：
 *  每第i个元素都要与前i个已排序好的元素比较。
 *  从第2个元素开始，1 + 2 + 3 + ... + n-1 = n*(n-1)/2 = O(n^2)。
 *
 * 最好时间复杂度（顺序）：
 * 每第i个元素都已经有序，只需要跟第i-1个元素比较一次。一共要比较n-1次，O(n)。如果序列基本有序的时候，
 * 可以使用直接插入排序算法。
 */
#include <stdio.h>

int arr[10] = {12, 14, 5, 3, 0, 1, 45, 8, 10, 10};

/**
 * 升序
 */
void insert_sort1(int arr[], int size)
{
    // 假设第1个元素是有序的, 从第二个元素开始遍历
    // 将后面无序的元素插入到前面有序的序列中
    for (int i = 1; i < size; i++) {
        // 先保存比较的元素
        int tmp = arr[i];
        int j = i-1;
        // 如果比较的元素大于已经排序好的元素,
        // 则排序好的元素往后移动位置，继续比较
        while (j >= 0 && arr[j] > tmp) {
            arr[j+1] = arr[j];
            j--;
        }
        // 找到插入的位置，插入元素
        arr[j+1] = tmp;
    }

    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);

    printf("\n");
}

int main (int argc, char **argv)
{

    insert_sort1(arr, 10);

    return 0;
}